package lc;

import ch4tree.BTreePrinter;
import ch4tree.Chapter;
import ch4tree.TreeNode;

public class FlattenBinaryTreeToLinkedList {
    public void flatten(TreeNode root) {
        if (root == null) {
        	return;
        }
        
        flatten(root.left);
        flatten(root.right);
        
        if (root.left != null) {
	        TreeNode k = root.left;
	        while (k.right != null) {
	        	k = k.right;
	        }
	        k.right = root.right;
	        root.right = root.left;
	        root.left = null;
        }                
    }
    
    public static void main(String ...strings) {
    	FlattenBinaryTreeToLinkedList sol = new FlattenBinaryTreeToLinkedList();
    	TreeNode node = Chapter.createMinimalBST(new int [] {1,2,3,4,5,6});
//    	TreeNode node = new TreeNode(2);
//    	node.left = new TreeNode(3);
    	BTreePrinter.printNode(node);
    	
    	sol.flatten(node);
    	BTreePrinter.printNode(node);
    }

}
